package ev.selection;

import ev.data.*;//need to add this line

import java.util.*;

public class Elitism implements Selection{

	public Population select(Population old, int limit)
	{
		//elitism: during each selection, there are 'elitist' elitists can survive before select
		int elitist = 5;
		Population res = new Population(old.getCities());
		int len = old.getPopulationSize()-elitist;
		Collections.sort(old.getPopulation());
		double[] proporty = new double[len];
		boolean[] flag = new boolean[len];
		for(int i = 0; i<elitist; i++){
			res.insert(old.getIndividual(0));
			old.remove(0);
		}
		proporty[0] = old.getIndividual(0).getQuality();
		for(int i = 1; i < len; i++){
			proporty[i] = proporty[i-1] + old.getIndividual(i).getQuality();
		}
		for(int i = 0; i < len; i++){
			proporty[i] = proporty[i] / proporty[len-1];
		}
		//
		int kickout = len + elitist - limit;
		Random r = new Random();
		double tmp;
		int index;
		for(int i = 0; i < kickout; i++){
			tmp = r.nextDouble();
			index = findout(proporty,tmp);
			if(flag[index]){
				i--;
			}
			else{
				flag[index] = true;
			}
		}
		for(int i=0; i<len; i++){
			if(!flag[i]){
				res.insert(old.getIndividual(i));
			}
		}
		return res;
	}
	
	public int findout(double[] proporty, double r){
		int res = 0;
		for(int i = 0; i<proporty.length; i++){
			if(r <= proporty[i]){
				res = i;
				break;
			}
		}
		return res;
	}
}
